package lc;
import java.util.*;
import org.junit.*;

import util.BracketUtils;
public class Ex207 {
    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Set<Integer> classes = new HashSet<>();
            Set<Integer> set = new HashSet<>();
    
            for (int i = 0; i < numCourses; i++) {
                set.add(i);
                classes.add(i);
            }
            Map<Integer, Set<Integer>> map = new HashMap<>();
            // Map<Integer, Integer> require = new HashMap<>();
            int[] req = new int[numCourses];
            for (int[] nums: prerequisites) {
                int pre = nums[1], post = nums[0];
                req[post]++;
                classes.remove(nums[0]);
                if (map.containsKey(pre)) {
                    map.get(pre).add(post);
                } else {
                    map.put(pre, new HashSet<>(Arrays.asList(post)));
                }
            }
            Queue<Integer> queue = new LinkedList<>(classes);
            while (!queue.isEmpty()) {
                int pre = queue.poll();
                set.remove(pre);
                Set<Integer> s = map.get(pre);
                if (s == null) continue;
                for (int next: s) {
                    req[next]--;
                    if (req[next] == 0) {
                        queue.offer(next);
                    }
                }
            }
            return set.isEmpty();
        }
    }


    @Test
    public void test() {
        Solution s = new Solution();
        int[][] nums = BracketUtils.to2DArray("[[1,0]]")        ;
        System.out.println(s.canFinish(2, nums));
    }
}
